package com.lihepeng.leecode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution34 {
    // 遍历完成解析，没有使用已经完成排序条件
    public int[] searchRange(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                list.add(i);
            }
        }
        if (list.size() == 0) {
            return new int[]{-1, -1};
        }
        int[] result = new int[]{list.get(0), list.get(list.size() - 1)};
        return result;
    }

    // 使用二分查找法完成
    // 先查找第一个等于target 位置，第一个大于target 位置-1
    public int[] searchRange1(int[] nums, int target) {
        int leftIndex = binarySearch(nums, target, true);
        int rightIndex = binarySearch(nums, target, false) - 1;
        if (leftIndex <= rightIndex && rightIndex < nums.length && nums[leftIndex] == target
                && nums[rightIndex] == target) {
            return new int[]{leftIndex, rightIndex};
        }
        return new int[]{-1, -1};
    }

    /**
     * 给定一个数组和目标值 查找 符合位置的索引开始和索引结束
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange02(int[] nums, int target) {
        int left =0,right = nums.length-1,ans = nums.length;
        while(left <= right){
            int mid = (left+right)/2;
            if (nums[left]<target){

            }
        }
        return null;
    }

    /**
     * 二分查找法
     *
     * @return
     */
    private int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
